package com.roy.galaxy.algorithm;

public class 最长公共前缀 {

    /**
     * 水平扫描方法：时间复杂度o(n),空间复杂度o(1)
     * @param strs
     * @return
     */
    public String longestCommonPrefix(String[] strs) {

        if (strs.length == 0) return "";
        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++)
            while (strs[i].indexOf(prefix) != 0) {
                prefix = prefix.substring(0, prefix.length() - 1);
                if (prefix.isEmpty()) return "";
            }
        return prefix;
    }

    public static void main(String[] args) {
        System.out.println(new 最长公共前缀().longestCommonPrefix(new String[]{"flower","flow","flight"}));
    }
}
